package org.hot100_0.leetcode148;

import org.leetcode.easy.ListNode;

public class Solution {
    public ListNode sortList(ListNode head) {

        ListNode res = split(head, null);
        return res;
    }

    private ListNode split(ListNode head, ListNode end) {

        if (head == end) {
            return head;
        }

        if (head.next == end) {
            head.next = null;
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast != end) {
            slow = slow.next;
            fast = fast.next;
            if (fast != end) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode left = split(head, mid);
        ListNode right = split(mid, end);

        return merge(left,right);
    }


    private ListNode merge(ListNode left,ListNode right){
        ListNode dummy = new ListNode(-1);
        ListNode list =  dummy;
        while (left!=null && right!=null){
            if (left.val<right.val){
                list.next=left;
                left=left.next;
            }else {
                list.next=right;
                right=right.next;
            }

            list=list.next;
        }

        if (left==null){
            list.next=right;
        }

        if (right==null){
            list.next=left;
        }

        return dummy.next;
    }


}
